import java.util.List;

//汉诺塔问题
//测试链接：https://leetcode.cn/problems/hanota-lcci/description/
public class Hanota {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        dfs(A,B,C,n);
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if(n < 1) return;

        //将n-1个盘子借助C放到B上
        dfs(A,C,B,n-1);

        //将盘子从A放到C上
        C.add(A.remove(A.size()-1));

        //将n-1个盘子借助A放到C上
        dfs(B,A,C,n-1);
    }
}
